// Created by WXX on 2021/10/22 21:06
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obs) {

        int m = obs.size(), n = obs[0].size();
        vector<vector<int>> f(m, vector<int>(n));
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (!obs[i][j]) {
                    if (!i && !j) f[i][j] = 1;
                    else {
                        if (i) f[i][j] += f[i - 1][j];
                        if (j) f[i][j] += f[i][j - 1];
                    }
                }
        return f[m - 1][n - 1];
    }
};

int main() {

    vector<vector<int>> obs = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
    cout << Solution().uniquePathsWithObstacles(obs) << endl;  // 2

    return 0;
}
